Generating subtour elimination constraints for the TSP from pure integer solutions.

The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph [Formula: see text] and non-negative distances d for every edge, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is a branch and cut approach. Usually the integrality constraints are relaxed first and all separation processes to identify violated inequalities are done on fractional solutions. In our approach we try to exploit the impressive performance of current ILP-solvers and work only with integer solutions without ever interfering with fractional solutions. We stick to a very simple ILP-model and relax the subtour elimination constraints only. The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible. These attempts are based on the clustering of vertices with additional insights gained from empirical observations and random graph theory. Computational results are performed on test instances taken from the TSPLIB95 and on random Euclidean graphs.

Erratum: Pferschy-Wenzig, E.-M.; et al. Does a Graphical Abstract Bring More Visibility to Your Paper? Molecules 2016, 21, 1247.

The authors wish to make the following change to their paper [1].[...].

Does a Graphical Abstract Bring More Visibility to Your Paper?

A graphical abstract (GA) represents a piece of artwork that is intended to summarize the main findings of an article for readers at a single glance. Many publishers currently encourage authors to supplement their articles with GAs, in the hope that such a convenient visual summary will facilitate readers with a clearer outline of papers that are of interest and will result in improved overall visibility of the respective publication. To test this assumption, we statistically compared publications with or without GA published in Molecules between March 2014 and March 2015 with regard to several output parameters reflecting visibility. Contrary to our expectations, manuscripts published without GA performed significantly better in terms of PDF downloads, abstract views, and total citations than manuscripts with GA. To the best of our knowledge, this is the first empirical study on the effectiveness of GA for attracting attention to scientific publications.

The Subset Sum game.

In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left. We look at the problem from a single agent point of view and show that finding an optimal sequence of items to select is an [Formula: see text]-hard problem. Therefore we propose two natural heuristic strategies and analyze their worst-case performance when (1) the opponent is able to play optimally and (2) the opponent adopts a greedy strategy. From a centralized perspective we observe that some known results on the approximation of the classical Subset Sum can be effectively adapted to the multi-agent version of the problem.

Exact solution of the robust knapsack problem.

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.

The role of morphology in combination with ploidy analysis in characterizing early gestational abortion.

Morphology in combination with flow cytometry is an inexpensive and fast tool to characterize important reasons for early gestational loss. Early partial hydatidiform moles are especially difficult to identify as not all have developed the typical histological features of central cistern formation and trophoblastic hyperplasia of the chorionic villi. Angiomatoid formation of the blood vessels, irregular chorionic villi, diffuse villous stromal fibrosis, trophoblastic pseudoinclusions, and pleomorphic trophoblast at the implantation site have therefore been proposed as additional morphological criteria. In our study, we investigated the correlation between morphological features and results of ploidy analysis to assess the additional criteria for practical use. Morphological features of the placentas of up to 13 weeks of gestation were evaluated on hematoxylin and eosin sections. Ploidy analysis was performed by flow cytometry on formalin-fixed, paraffin-embedded tissue. Statistical analysis was performed by binary logistic regression. One hundred fifty samples were included in the study. Of the samples, 23 were triploid, 19 were tetraploid, and the remaining ones were diploid. Statistical analysis showed a poor predictive power based on all morphological criteria alone. The most important result of this study was the identification of five triploid placentas that showed diffuse fibrosis of the chorionic villi, angiomatoid changes of the blood vessels, trophoblastic pseudoinclusions, and focal pleomorphic changes at the implantation site, but none of the classical morphological features of triploid pregnancies were identified. Our study demonstrates that the use of additional morphological criteria increases the number of missed abortions with identified causes for pregnancy loss.